<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
    <meta name="keywords" content="Hexo Theme Keep">
    <meta name="description" content="宋标的个人博客">
    <meta name="author" content="宋标">
	<meta name="referrer" content="no-referrer"/>
    
    <title>
        
            leetcode994. 腐烂的橘子 |
        
        宋标的blog
    </title>
    
<link rel="stylesheet" href="/css/style.css">

    <link rel="shortcut icon" href="/images/logo.svg">
    
<link rel="stylesheet" href="/css/font-awesome.min.css">

    <script id="hexo-configurations">
    let KEEP = window.KEEP || {};
    KEEP.hexo_config = {"hostname":"song_biao.gitee.io","root":"/","language":"zh-CN","path":"search.xml"};
    KEEP.theme_config = {"toc":{"enable":true,"number":true,"expand_all":true,"init_open":true},"style":{"primary_color":"#0066CC","avatar":"/images/avatar.svg","favicon":"/images/logo.svg","article_img_align":"left","left_side_width":"260px","content_max_width":"920px","hover":{"shadow":false,"scale":false},"first_screen":{"enable":true,"background_img":"/images/bg.svg","description":"while(alive()) study();"},"scroll":{"progress_bar":{"enable":false},"percent":{"enable":false}}},"local_search":{"enable":true,"preload":false},"code_copy":{"enable":false,"style":"default"},"pjax":{"enable":false},"lazyload":{"enable":false},"version":"3.4.5"};
    KEEP.language_ago = {"second":"%s 秒前","minute":"%s 分钟前","hour":"%s 小时前","day":"%s 天前","week":"%s 周前","month":"%s 个月前","year":"%s 年前"};
  </script>
<meta name="generator" content="Hexo 6.1.0"></head>


<body>
<div class="progress-bar-container">
    

    
</div>


<main class="page-container">

    

    <div class="page-main-content">

        <div class="page-main-content-top">
            <header class="header-wrapper">

    <div class="header-content">
        <div class="left">
            
            <a class="logo-title" href="/">
                宋标的blog
            </a>
        </div>

        <div class="right">
            <div class="pc">
                <ul class="menu-list">
                    
                        <li class="menu-item">
                            <a class=""
                               href="/"
                            >
                                首页
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/tags"
                            >
                                标签
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/categories"
                            >
                                分类
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/archives"
                            >
                                归档
                            </a>
                        </li>
                    
                    
                        <li class="menu-item search search-popup-trigger">
                            <i class="fas fa-search"></i>
                        </li>
                    
                </ul>
            </div>
            <div class="mobile">
                
                    <div class="icon-item search search-popup-trigger"><i class="fas fa-search"></i></div>
                
                <div class="icon-item menu-bar">
                    <div class="menu-bar-middle"></div>
                </div>
            </div>
        </div>
    </div>

    <div class="header-drawer">
        <ul class="drawer-menu-list">
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/">首页</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/tags">标签</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/categories">分类</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/archives">归档</a>
                </li>
            
        </ul>
    </div>

    <div class="window-mask"></div>

</header>


        </div>

        <div class="page-main-content-middle">

            <div class="main-content">

                
                    <div class="fade-in-down-animation">
    <div class="article-content-container">

        <div class="article-title">
            <span class="title-hover-animation">leetcode994. 腐烂的橘子</span>
        </div>

        
            <div class="article-header">
                <div class="avatar">
                    <img src="/images/avatar.svg">
                </div>
                <div class="info">
                    <div class="author">
                        <span class="name">宋标</span>
                        
                            <span class="author-label">Lv5</span>
                        
                    </div>
                    <div class="meta-info">
                        <div class="article-meta-info">
    <span class="article-date article-meta-item">
        <i class="fas fa-edit"></i>&nbsp;
        <span class="pc">2022-04-06 19:04:16</span>
        <span class="mobile">2022-04-06 19:04</span>
    </span>
    
        <span class="article-categories article-meta-item">
            <i class="fas fa-folder"></i>&nbsp;
            <ul>
                
                    <li>
                        <a href="/categories/leetcode/">leetcode</a>&nbsp;
                    </li>
                
            </ul>
        </span>
    
    
        <span class="article-tags article-meta-item">
            <i class="fas fa-tags"></i>&nbsp;
            <ul>
                
                    <li>
                        <a href="/tags/bfs/">bfs</a>&nbsp;
                    </li>
                
                    <li>
                        | <a href="/tags/%E5%A4%9A%E6%BA%90bfs/">多源bfs</a>&nbsp;
                    </li>
                
            </ul>
        </span>
    

    
    
    
    
</div>

                    </div>
                </div>
            </div>
        

        <div class="article-content markdown-body">
            <meta name="referrer" content="no-referrer" />

<h2 id="题目"><a href="#题目" class="headerlink" title="题目"></a>题目</h2><p>在给定的 <code>m x n</code> 网格 <code>grid</code> 中，每个单元格可以有以下三个值之一：</p>
<ul>
<li>值 0 代表空单元格；</li>
<li>值 1 代表新鲜橘子；</li>
<li>值 2 代表腐烂的橘子。</li>
</ul>
<p>每分钟，腐烂的橘子<strong>周围 4 个方向上相邻</strong>的新鲜橘子都会腐烂。</p>
<p>返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。</p>
<p><strong>示例 1：</strong><br><img src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/02/16/oranges.png"></p>
<blockquote>
<p>输入：grid &#x3D; [[2,1,1],[1,1,0],[0,1,1]]<br>输出：4</p>
</blockquote>
<p><strong>示例 2：</strong></p>
<blockquote>
<p>输入：grid &#x3D; [[2,1,1],[0,1,1],[1,0,1]]<br>输出：-1<br>解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。</p>
</blockquote>
<p><strong>示例 3：</strong></p>
<blockquote>
<p>输入：grid &#x3D; [[0,2]]<br>输出：0<br>解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。
 </p>
</blockquote>
<p><strong>提示：</strong></p>
<ul>
<li>m &#x3D;&#x3D; grid.length</li>
<li>n &#x3D;&#x3D; grid[i].length</li>
<li>1 &lt;&#x3D; m, n &lt;&#x3D; 10</li>
<li>grid[i][j] 仅为 0、1 或 2</li>
</ul>
<p>来源：力扣（LeetCode）<br>链接：<a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/rotting-oranges" >https://leetcode-cn.com/problems/rotting-oranges<i class="fas fa-external-link-alt"></i></a><br>著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。</p>
<h2 id="题解"><a href="#题解" class="headerlink" title="题解"></a>题解</h2><p>注意：<br>题目中存在多个腐烂橘子(多个源点)，所有腐烂的橘子会<strong>同时扩散</strong></p>
<p>思路:</p>
<ol>
<li>将所有腐烂橘子看作一个整体,赋一个初始值0，向外扩散。</li>
<li>被扩散腐烂的橘子消耗的分钟等于扩散点的值+1，依次继续扩散，直到扩散结束。</li>
</ol>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="type">int</span>[][] xy= &#123;&#123;<span class="number">0</span>,<span class="number">1</span>&#125;,&#123;<span class="number">1</span>,<span class="number">0</span>&#125;,&#123;-<span class="number">1</span>,<span class="number">0</span>&#125;,&#123;<span class="number">0</span>,-<span class="number">1</span>&#125;&#125;;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">public</span> <span class="type">int</span> <span class="title function_">orangesRotting</span><span class="params">(<span class="type">int</span>[][] grid)</span> &#123;</span><br><span class="line">        LinkedList&lt;<span class="type">int</span>[]&gt; queue = <span class="keyword">new</span> <span class="title class_">LinkedList</span>();</span><br><span class="line">        Map&lt;Integer,Integer&gt; depth = <span class="keyword">new</span> <span class="title class_">HashMap</span>();</span><br><span class="line">        <span class="type">int</span> m,n;</span><br><span class="line">        <span class="type">int</span> <span class="variable">frish</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line">        m = grid.length;</span><br><span class="line">        n = grid[<span class="number">0</span>].length;</span><br><span class="line">        </span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>;i&lt;m;++i)&#123;</span><br><span class="line">            <span class="keyword">for</span>(<span class="type">int</span> j=<span class="number">0</span>;j&lt;n;++j)&#123;</span><br><span class="line">                <span class="type">int</span> <span class="variable">cur</span> <span class="operator">=</span> grid[i][j];</span><br><span class="line">                <span class="keyword">if</span>(cur==<span class="number">2</span>)&#123;</span><br><span class="line">                    <span class="comment">//初始0分钟</span></span><br><span class="line">                    depth.put(i*n+j,<span class="number">0</span>);</span><br><span class="line">                    <span class="comment">//将所有腐烂的橘子预先加入队列中</span></span><br><span class="line">                    queue.addFirst(<span class="keyword">new</span> <span class="title class_">int</span>[]&#123;i,j&#125;);</span><br><span class="line">                &#125;<span class="keyword">else</span> <span class="keyword">if</span>(cur==<span class="number">1</span>)&#123;</span><br><span class="line">                    <span class="comment">//统计所有新鲜的橘子数量</span></span><br><span class="line">                    ++frish;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//最后一个腐烂橘子花费的时间</span></span><br><span class="line">        <span class="type">int</span> <span class="variable">ans</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line">        <span class="comment">// 腐烂扩散(广度优先遍历)</span></span><br><span class="line">        <span class="keyword">while</span>(!queue.isEmpty())&#123;</span><br><span class="line">            <span class="type">int</span>[] cell = queue.poll();</span><br><span class="line">            <span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> cell[<span class="number">0</span>],j = cell[<span class="number">1</span>];</span><br><span class="line">            <span class="keyword">for</span>(<span class="type">int</span> k=<span class="number">0</span>;k&lt;<span class="number">4</span>;++k)&#123;</span><br><span class="line">                <span class="type">int</span> <span class="variable">x</span> <span class="operator">=</span> i+xy[k][<span class="number">0</span>];</span><br><span class="line">                <span class="type">int</span> <span class="variable">y</span> <span class="operator">=</span> j+xy[k][<span class="number">1</span>];</span><br><span class="line">                <span class="keyword">if</span>(x&gt;=<span class="number">0</span> &amp;&amp; x&lt;m &amp;&amp; y&gt;=<span class="number">0</span> &amp;&amp; y&lt;n &amp;&amp; grid[x][y]==<span class="number">1</span>)&#123;</span><br><span class="line">                    grid[x][y]=<span class="number">2</span>;</span><br><span class="line">                    <span class="comment">//持续扩散</span></span><br><span class="line">                    queue.addLast(<span class="keyword">new</span> <span class="title class_">int</span>[]&#123;x,y&#125;);</span><br><span class="line">                    <span class="comment">//花费的分钟等于传播点的值+1</span></span><br><span class="line">                    ans = depth.get(i*n+j)+<span class="number">1</span>;</span><br><span class="line">                    depth.put(x*n+y,ans);</span><br><span class="line">                    <span class="comment">//新鲜橘子数量减1</span></span><br><span class="line">                    --frish;</span><br><span class="line">                &#125;</span><br><span class="line">                </span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//如果还存在新鲜橘子则返回-1</span></span><br><span class="line">        <span class="keyword">return</span> frish==<span class="number">0</span>?ans:-<span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
        </div>

        

        
            <ul class="post-tags-box">
                
                    <li class="tag-item">
                        <a href="/tags/bfs/">#bfs</a>&nbsp;
                    </li>
                
                    <li class="tag-item">
                        <a href="/tags/%E5%A4%9A%E6%BA%90bfs/">#多源bfs</a>&nbsp;
                    </li>
                
            </ul>
        

        
            <div class="article-nav">
                
                    <div class="article-prev">
                        <a class="prev"
                           rel="prev"
                           href="/2022/04/07/leetcode46-%E5%85%A8%E6%8E%92%E5%88%97/"
                        >
                            <span class="left arrow-icon flex-center">
                              <i class="fas fa-chevron-left"></i>
                            </span>
                            <span class="title flex-center">
                                <span class="post-nav-title-item">leetcode46. 全排列</span>
                                <span class="post-nav-item">上一篇</span>
                            </span>
                        </a>
                    </div>
                
                
                    <div class="article-next">
                        <a class="next"
                           rel="next"
                           href="/2022/04/06/leetcode206-%E5%8F%8D%E8%BD%AC%E9%93%BE%E8%A1%A8/"
                        >
                            <span class="title flex-center">
                                <span class="post-nav-title-item">leetcode206. 反转链表</span>
                                <span class="post-nav-item">下一篇</span>
                            </span>
                            <span class="right arrow-icon flex-center">
                              <i class="fas fa-chevron-right"></i>
                            </span>
                        </a>
                    </div>
                
            </div>
        

        
            <div class="comment-container">
                <div class="comments-container">
    <div id="comment-anchor"></div>
    <div class="comment-area-title">
        <i class="fas fa-comments">&nbsp;评论</i>
    </div>
    

        
            
    <div class="valine-container">
        <script 
                src="//cdn.jsdelivr.net/npm/valine@latest/dist/Valine.min.js"></script>
        <div id="vcomments"></div>
        <script >
            function loadValine() {
                new Valine({
                    el: '#vcomments',
                    appId: 'GaPFQduCGtJWQ2Cmma9jEfx1-gzGzoHsz',
                    appKey: 'h9IWwxU3RWqBFCD4CqERkpuv',
                    meta: ['nick', 'mail', 'link'],
                    avatar: 'wavatar',
                    enableQQ: true,
                    placeholder: '',
                    lang: 'zh-CN'.toLowerCase()
                });

                function getAuthor(language) {
                    switch (language) {
                        case 'en':
                            return 'Author';
                        case 'zh-CN':
                            return '博主';
                        default:
                            return 'Master';
                    }
                }

                // Add "Author" identify
                const getValineDomTimer = setInterval(() => {
                    const vcards = document.querySelectorAll('#vcomments .vcards .vcard');
                    if (vcards.length > 0) {
                        let author = '宋标';

                        if (author) {
                            for (let vcard of vcards) {
                                const vnick_dom = vcard.querySelector('.vhead .vnick');
                                const vnick = vnick_dom.innerHTML;
                                if (vnick === author) {
                                    vnick_dom.innerHTML = `${vnick} <span class="author">${getAuthor(KEEP.hexo_config.language)}</span>`
                                }
                            }
                        }
                        clearInterval(getValineDomTimer);
                    } else {
                        clearInterval(getValineDomTimer);
                    }
                }, 2000);
            }

            if ('false') {
                const loadValineTimeout = setTimeout(() => {
                    loadValine();
                    clearTimeout(loadValineTimeout);
                }, 1000);
            } else {
                window.addEventListener('DOMContentLoaded', loadValine);
            }
        </script>
    </div>



        
    
</div>

            </div>
        
    </div>
</div>


                
            </div>

        </div>

        <div class="page-main-content-bottom">
            <footer class="footer">
    <div class="info-container">
        <div class="copyright-info info-item">
            &copy;
            
              <span>2020</span>
              -
            
            2023&nbsp;<i class="fas fa-heart icon-animate"></i>&nbsp;<a href="/">宋标</a>
        </div>
        
        <div class="theme-info info-item">
            由 <a target="_blank" href="https://hexo.io">Hexo</a> 驱动&nbsp;|&nbsp;主题&nbsp;<a class="theme-version" target="_blank" href="https://github.com/XPoet/hexo-theme-keep">Keep v3.4.5</a>
        </div>
        
        
    </div>
</footer>

        </div>
    </div>

    
        <div class="post-tools">
            <div class="post-tools-container">
    <ul class="tools-list">
        <!-- TOC aside toggle -->
        
            <li class="tools-item page-aside-toggle">
                <i class="fas fa-outdent"></i>
            </li>
        

        <!-- go comment -->
        
            <li class="go-comment">
                <i class="fas fa-comment"></i>
            </li>
        
    </ul>
</div>

        </div>
    

    <div class="right-bottom-side-tools">
        <div class="side-tools-container">
    <ul class="side-tools-list">
        <li class="tools-item tool-font-adjust-plus flex-center">
            <i class="fas fa-search-plus"></i>
        </li>

        <li class="tools-item tool-font-adjust-minus flex-center">
            <i class="fas fa-search-minus"></i>
        </li>

        <li class="tools-item tool-expand-width flex-center">
            <i class="fas fa-arrows-alt-h"></i>
        </li>

        <li class="tools-item tool-dark-light-toggle flex-center">
            <i class="fas fa-moon"></i>
        </li>

        <!-- rss -->
        

        
            <li class="tools-item tool-scroll-to-top flex-center">
                <i class="fas fa-arrow-up"></i>
            </li>
        

        <li class="tools-item tool-scroll-to-bottom flex-center">
            <i class="fas fa-arrow-down"></i>
        </li>
    </ul>

    <ul class="exposed-tools-list">
        <li class="tools-item tool-toggle-show flex-center">
            <i class="fas fa-cog fa-spin"></i>
        </li>
        
    </ul>
</div>

    </div>

    
        <aside class="page-aside">
            <div class="post-toc-wrap">
    <div class="post-toc">
        <ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#%E9%A2%98%E7%9B%AE"><span class="nav-number">1.</span> <span class="nav-text">题目</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E9%A2%98%E8%A7%A3"><span class="nav-number">2.</span> <span class="nav-text">题解</span></a></li></ol>
    </div>
</div>
        </aside>
    

    <div class="image-viewer-container">
    <img src="">
</div>


    
        <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
          <span class="search-input-field-pre">
            <i class="fas fa-keyboard"></i>
          </span>
            <div class="search-input-container">
                <input autocomplete="off"
                       autocorrect="off"
                       autocapitalize="off"
                       placeholder="搜索..."
                       spellcheck="false"
                       type="search"
                       class="search-input"
                >
            </div>
            <span class="popup-btn-close">
                <i class="fas fa-times"></i>
            </span>
        </div>
        <div id="search-result">
            <div id="no-result">
                <i class="fas fa-spinner fa-pulse fa-5x fa-fw"></i>
            </div>
        </div>
    </div>
</div>

    

</main>




<script src="/js/utils.js"></script>

<script src="/js/main.js"></script>

<script src="/js/header-shrink.js"></script>

<script src="/js/back2top.js"></script>

<script src="/js/dark-light-toggle.js"></script>



    
<script src="/js/local-search.js"></script>







<div class="post-scripts">
    
        
<script src="/js/left-side-toggle.js"></script>

<script src="/js/libs/anime.min.js"></script>

<script src="/js/toc.js"></script>

    
</div>



</body>
</html>
